package com.example.leetcode.c1_c100.c74;
/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 示例 1:
 *
 * 输入:
 * matrix = [
 *   [1,   3,  5,  7],
 *   [10, 11, 16, 20],
 *   [23, 30, 34, 50]
 * ]
 * target = 3
 * 输出: true
 * 示例 2:
 *
 * 输入:
 * matrix = [
 *   [1,   3,  5,  7],
 *   [10, 11, 16, 20],
 *   [23, 30, 34, 50]
 * ]
 * target = 13
 * 输出: false
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * 搜索二维矩阵
 * @author zhanpengguo
 * @date 2020-09-18 14:43
 */
public class Solution {

    //思路：先对最后一列二分查找，确定target所在行；然后对所在行二分查找
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rowSize = matrix.length - 1;
        int colSize = matrix[0].length - 1;
        // 先确定目标值所在行
        // 二分查找
        int row = -1;
        int first = 0;
        int last = rowSize;
        while (last > first) {
            int middle = first + (last - first) / 2;
            int firstValue = matrix[first][colSize];
            int middleValue = matrix[middle][colSize];
            int lastValue = matrix[last][colSize];
            if (target < firstValue) {
                row = first;
                break;
            }
            if (target == firstValue || target == middleValue || target == lastValue) {
                return true;
            }
            if (target > lastValue) {
                return false;
            }
            if (target > middleValue) {
                first = middle + 1;
            } else {
                last = middle;
            }
        }
        if (row == -1) {
            row = last;
        }
        // 对所在行进行二分查找
        first = 0;
        last = colSize;
        while (last > first) {
            int middle = first + (last - first) / 2;
            int firstValue = matrix[row][first];
            int middleValue = matrix[row][middle];
            int lastValue = matrix[row][last];
            if (target < firstValue) {
                return false;
            }
            if (target == firstValue || target == middleValue || target == lastValue) {
                return true;
            }
            if (target > lastValue) {
                return false;
            }
            if (target > middleValue) {
                first = middle + 1;
            } else {
                last = middle;
            }
        }
        return matrix[row][first] == target || matrix[row][last] == target;
    }


    public static void main(String[] args) {
//        int[][] matrix = {{1,   3,  5,  7},{10, 11, 16, 20},{23, 30, 34, 50}};
        int[][] matrix = {{1},{3}};
        Solution solution = new Solution();
        boolean b = solution.searchMatrix(matrix, 1);
        System.out.println(b);
    }
}
